package 二叉树;

import java.util.LinkedList;
import java.util.Queue;

/**
 * https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/
 */
public class _104_二叉树的最大深度 {
    /**
     * 利用队列 实现层序遍历 遍历一次高度+1
     * @param root
     * @return
     */
     public int maxDepth1(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList();
        int height = 0;
        int levelSize = 1;
        if(root == null) return height;

         queue.offer(root);
         while(!queue.isEmpty()){
            TreeNode node =  queue.poll();
            levelSize--;
            if(node.left!=null) queue.offer(node.left);
            if(node.right!=null) queue.offer(node.right);
            if(levelSize == 0){
                height++;
                levelSize = queue.size();
            }
         }
         return height;
    }

    //递归
    //每个节点的高度等于 子节点中最大的高度+1
    public int maxDepth(TreeNode root) {
        if(root == null) return 0;

       return 1+ Math.max(maxDepth(root.left),maxDepth(root.right));
    }
}
